package main

// Definition for singly-linked list.
type ListNode struct {
	Val  int
	Next *ListNode
}

// addTwoNumbers:两数相加
// 解法1：迭代法
func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
	total := 0           // 两个元素之和
	next1 := 0           // 是否需要进位
	result := ListNode{} // 最终的结果集
	cur := &result       // 用于辅助移动的链表
	for {
		if l1 == nil || l2 == nil {
			break
		}
		total = l1.Val + l2.Val + next1
		cur.Next = &ListNode{Val: total % 10}
		next1 = total / 10
		l1 = l1.Next
		l2 = l2.Next
		cur = cur.Next
	}

	for { // l1没有走完
		if l1 == nil {
			break
		}
		total = l1.Val + next1
		cur.Next = &ListNode{Val: total % 10}
		next1 = total / 10
		l1 = l1.Next
		cur = cur.Next
	}

	for { // l2没有走完
		if l2 == nil {
			break
		}
		total = l2.Val + next1
		cur.Next = &ListNode{Val: total % 10}
		next1 = total / 10
		l2 = l2.Next
		cur = cur.Next
	}

	if next1 != 0 { // 需要新增节点保留进位值
		cur.Next = &ListNode{Val: next1}
	}

	return result.Next
}

// addTwoNumbers:两数相加
// 解法2：递归法
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode {
	total := l1.Val + l2.Val
	next1 := total / 10
	res := ListNode{Val: total % 10}
	if l1.Next != nil || l2.Next != nil || next1 != 0 {
		if l1.Next != nil {
			l1 = l1.Next
		} else {
			l1 = &ListNode{Val: 0}
		}

		if l2.Next != nil {
			l2 = l2.Next
		} else {
			l2 = &ListNode{Val: 0}
		}

		l1.Val = l1.Val + next1
		res.Next = addTwoNumbers2(l1, l2)
	}
	return &res
}
